【剑指Offer I】34. 二叉树中和为某一值的路径
题目
给你二叉树的根节点 root
和一个整数目标和 targetSum
,找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例
输入:root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出:[[5,4,11,2],[5,8,4,5]]
解答
思路
深度优先搜索每一条根到叶子节点的路径,其实就是先序遍历。
本题是求所有可行解方案,所以需要保存中间路径,在满足条件时加入最后的答案。在回溯时需要恢复上一层的路径,即把上一层的节点删掉。
代码
1 | /** |
复杂度
- 时间复杂度
O(N)
:访问树的所有节点。 - 空间复杂度
O(N)
:系统栈空间。
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 namespace LANG!
评论